BOJ_17779_게리맨더링2

BOJ_17471_게리맨더링과 다르게 구현, 완전탐색으로 푸는 문제
반복문을 돌면서 기준이 될 x, y를 산정하고
4개의 범위에 해당하는 인구 수를 세어주면 된다

범위를 잡는 것이 가장 까다로운데, 문제에 충실하게 구현하면 된다

package BJO;  
  
import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.Arrays;  
import java.util.stream.Stream;  
  
public class BJO_17779_게리멘더링2 {  
  
    static int N;  
    static int[][] A;  
    static int allPersons;  
    static int min = Integer.MAX_VALUE;  
  
    public static void main(String[] args) throws IOException {  
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
       N = Integer.parseInt(br.readLine());  
       A = new int[N][N];  
  
       for (int i = 0; i < N; i++) {  
          A[i] = Stream.of(br.readLine().split(" ")).mapToIntparseInt).toArray(;  
          allPersons += Arrays.stream(A[i]).sum();  
       }  
  
       for (int i = 0; i < N; i++) {  
          for (int j = 0; j < N; j++) {  
             for (int d1 = 1; d1 < N; d1++) {  
                for (int d2 = 1; d2 < N; d2++) {  
                   if (j + d1 + d2 < N && i - d1 >= 0 && i + d2 < N) {  
                      solution(i, j, d1, d2);  
                   }  
                }  
             }  
          }  
       }  
       System.out.println(min);  
    }  
  
    static void print(int[][] check) {  
       for (int i = 0; i < N; i++) {  
          for (int j = 0; j < N; j++) {  
             System.out.print(check[i][j] + " ");  
          }  
          System.out.println();  
       }  
       System.out.println();  
    }  
  
    static void solution(int y, int x, int d1, int d2) {  
       int[][] check = new int[N][N];  
  
       for (int i = 0; i <= d1; i++) {  
          check[y - i][x + i] = 5;  
          check[y + d2 - i][x + d2 + i] = 5;  
       }  
  
       for (int i = 0; i <= d2; i++) {  
          check[y + i][x + i] = 5;  
          check[y - d1 + i][x + d1 + i] = 5;  
       }  
  
       int[] persons = new int[5];  
  
       Loop:  
       for (int i = 0; i < y; i++) {  
          for (int j = 0; j <= x + d1; j++) {  
             if (check[i][j] == 5) {  
                continue Loop;  
             } else if (check[i][j] == 0) {  
                persons[0] += A[i][j];  
                check[i][j] = 1;  
             }  
          }  
       }  
  
       Loop:  
       for (int i = y; i < N; i++) {  
          for (int j = 0; j < x + d2; j++) {  
             if (check[i][j] == 5) {  
                continue Loop;  
             } else if (check[i][j] == 0) {  
                persons[1] += A[i][j];  
                check[i][j] = 2;  
             }  
          }  
       }  
  
       Loop:  
       for (int i = 0; i <= y - d1 + d2; i++) {  
          for (int j = N - 1; j > x + d1; j--) {  
             if (check[i][j] == 5) {  
                continue Loop;  
             }  
  
             if (check[i][j] == 0) {  
                persons[2] += A[i][j];  
                check[i][j] = 3;  
             }  
          }  
       }  
  
       Loop:  
       for (int i = N - 1; i >= y - d1 + d2; i--) {  
          for (int j = N - 1; j >= x + d2; j--) {  
             if (check[i][j] == 5) {  
                continue Loop;  
             }  
  
             if (check[i][j] == 0) {  
                persons[3] += A[i][j];  
                check[i][j] = 4;  
             }  
          }  
       }  
  
//     print(check);  
  
       persons[4] = allPersons - Arrays.stream(persons).sum();  
       min = Math.min(Arrays.stream(persons).max().getAsInt() - Arrays.stream(persons).min().getAsInt(), min);  
    }  
}